package com.LeeCode;

/**
 * 元素和小于等于阈值的正方形的最大边长
 */

public class Code1292 {
    public static void main(String[] args) {

    }

    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length, n = mat[0].length;
        int[][] preSum = new int[m + 1][n + 1];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                preSum[i + 1][j + 1] = mat[i][j]
                        + preSum[i][j + 1]     // 上
                        + preSum[i + 1][j]     // 左
                        - preSum[i][j];        // 左上
            }
        }

        int maxLen = Math.min(m, n);

        // 从大到小枚举边长
        for (int len = maxLen; len >= 1; len--) {
            for (int i = 0; i <= m - len; i++) {  // 注意：<=
                for (int j = 0; j <= n - len; j++) {  // 注意：<=
                    int r = i + len - 1;
                    int c = j + len - 1;
                    int sum = preSum[r + 1][c + 1]
                            - preSum[i][c + 1]
                            - preSum[r + 1][j]
                            + preSum[i][j];
                    if (sum <= threshold) {
                        return len;
                    }
                }
            }
        }
        return 0;
    }
}
